package com.fe.class08;

import java.util.Arrays;

/**
 * @Description 桶排序—基数排序(桶表示进制的遍历，十进制，则有十个桶)
 * 基数排序要求，样本是10进制的正整数
 * @Author sosuke :-)
 * @Date 2022/1/12 22:07
 */
public class Code04_RadixSort {
    /**
     * 基数排序思想：我们人类排序数字时，就是先按照百位数排序，百位数相同则按照十位数排序，十位数相同则按照个位数排序
     * 实现时，我们假设数组已经按照十位数排序，且十位数相同则按照个位数排序，我们则只需要对数组按照百位数排序，百位数相同则按照数组现有的顺序来
     * 要实现百位数相同就按照数组现有顺序来，即要先进先出，所以桶要用队列实现；
     * 要实现我们假设的数组顺序，则要对数组按照个位数排序，之后，再对数组按照十位数排序，最后按照百位数排序
     * 十进制数，0～9，所以准备十个桶（相当于队列，先进先出）
     * 遍历数组arr，找出最大值的位数，假设是三位数，则需要从个位开始到百位，共循环三次
     * 第一次遍历个位数，如果个位数为0，则进0号桶，如果个位数为1，则进1号桶，...，从0号桶开始依次倒出数据（此时数组是按照个位数排序的）
     * 在第一次倒出的数据上，遍历十位数，分别进对应的桶，再从0号桶开始依次倒出数据（此时数组是按照十位数排序的，相同则根据个位数排序，因为是按照之前个位数的排序来进桶的）
     * 在第二次倒出的数据上，遍历百位数，分别进对应的桶，再从0号桶开始依次倒出数据（此时数组是按照百位数排序的，相同则根据十位数排序，因为是按照之前十位数的排序来进桶的）
     */

    /**
     * 只适用于非负数
     * 如果最大数有三位，则遍历三次，每次arr需要进桶出桶
     * 如果最大数的位数较多，则复杂度O(N*log10^max)  log以10为底，max的对数，即最大值的位数
     * @param arr
     */
    public static void radixSort(int[] arr) {
        if (null == arr || arr.length < 2) return;
        radixSort(arr, 0, arr.length - 1, maxBits(arr));
    }

    /**
     * 倒序遍历arr
     * 个位数排序时，看某个数组元素个位数为j，如果知道数组中元素个位数<=j的有多少个，就知道这个元素的排序位置了，依次类推，按照十位数、百位数排序
     * @param arr
     * @param L
     * @param R
     * @param maxBits
     */
    private static void radixSort(int[] arr, int L, int R, int maxBits) {
        if (L >= R) return;
        final int radix = 10; // 十进制
        int[] help = new int[R - L + 1];
        // d=1表示个位数，从个位数开始
        for (int d = 1; d <= maxBits; d++) {
            // 10个空间
            int[] counts = new int[radix];
            // 遍历arr
            // count[k] 表示arr中当前位(d位)是k的数字有多少个
            for (int i = L; i <= R; i++) {
                int j = getDigit(arr[i], d);
                counts[j]++;
            }
            // 计算前缀和
            // count[k] 表示arr中当前位(d位)<=k的数字有多少个
            for (int i = 1; i < counts.length; i++) {
                counts[i] = counts[i] + counts[i - 1];
            }
            // 倒序遍历arr
            for (int i = R; i >= L; i--) {
                int j = getDigit(arr[i], d);// 假设d=1，则arr[i]的个位数位j
                help[counts[j] - 1] = arr[i];// arr中个位数<=j的有counts[j]个，所以arr[i]应该排在counts[j]-1的位置
                counts[j]--;// arr中个位数<=j的有counts[j]-1个
            }
            // 将help赋值给arr
            for (int i = 0; i < help.length; i++) {
                arr[L + i] = help[i];
            }
        }
    }

    /**
     * 计算num第d位上的数
     * 计算十位数上的数，num/10，再对10取余数
     * 计算百位数上的数，num/100，再对10取余数
     * @param num
     * @param d
     * @return
     */
    private static int getDigit(int num, int d) {
        return (num / (int) (Math.pow(10, d - 1))) % 10;
    }

    /**
     * 计算数组元素的最大值的十进制位数
     *
     * @param arr
     * @return
     */
    private static int maxBits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            max = Math.max(max, num);
        }
        int ans = 0;
        while (max != 0) {
            max = max / 10;
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        int testTime = 500000; // 测试次数
        int maxSize = 10; // 数组数据个数
        int maxValue = 100; // 数组中最大值
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            radixSort(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("Fuck");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return;
            }
        }
        System.out.println("Nice");
        int[] arr = generateRandomArray(maxSize, maxValue);
        System.out.println(Arrays.toString(arr));
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

}
